import { testSort } from "hy-algokit";

export default function shellSort(arr: number[]): number[] {
  const n = arr.length;
  let gap = Math.floor(n / 2);

  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      let j = i;
      const num = arr[i];

      while (j > gap - 1 && arr[j - gap] > num) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }

      arr[j] = num;
    }

    gap = Math.floor(gap / 2);
  }

  return arr;
}

testSort(shellSort);
